package leetcode.method.back_tracking;


import java.util.*;

public class Program17letterCombinationforTelephoneNumber {

    public Program17letterCombinationforTelephoneNumber() {
    }
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) {
            return new ArrayList<>();
        }
        // 初始化映射表
        Map<Character, List<String>> numberLetterMap = new HashMap<>(16);
        numberLetterMap.put('2', Arrays.asList("a","b","c"));
        numberLetterMap.put('3', Arrays.asList("d","e","f"));
        numberLetterMap.put('4', Arrays.asList("g","h","i"));
        numberLetterMap.put('5', Arrays.asList("j","k","l"));
        numberLetterMap.put('6', Arrays.asList("m","n","o"));
        numberLetterMap.put('7', Arrays.asList("p","q","r","s"));
        numberLetterMap.put('8', Arrays.asList("t","u","v"));
        numberLetterMap.put('9', Arrays.asList("w","x","y","z"));

        List<String> res = new ArrayList<>();
        letterCombinations(digits, 0, numberLetterMap, "", res);

        return res;
    }

    public void letterCombinations(String digits, int index, Map<Character, List<String>> numberLetterMap, String tmpRes, List<String> res) {
        List<String> strings = numberLetterMap.get(digits.charAt(index));
        if (digits.length() == index + 1) {
            for (String str : strings) {
                res.add(tmpRes + str);
            }
        } else {
            for (String str : strings) {
                letterCombinations(digits, index+ 1, numberLetterMap, tmpRes + str, res);
            }
        }
    }

    public static void main(String[] args) {

        Program17letterCombinationforTelephoneNumber program = new Program17letterCombinationforTelephoneNumber();
        String digits = "23";
        System.out.println(program.letterCombinations(digits));
    }
}
